package algorithm_demo.demo02;

/**
 * 设计一个算法，找出二叉搜索树中指定节点的“下一个”节点（也即中序后继）。
 * <p>
 * 如果指定节点没有对应的“下一个”节点，则返回null。
 *
 * @author Api
 * @date 2023/2/11 23:35
 */
public class Code05_InorderSuccessor {
    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }

    public static TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
        //这里注意二叉搜索树的思路
        //若它的左子树不为空，则左子树上所有节点的值都小于根节点的值
        //若它的右子树不为空，则右子树上所有节点的值都大于根节点的值
        //它的左右子树也分别为二叉搜索树
        //中序遍历出来就是单调递增的
        TreeNode cur = root, ans = null;
        while (cur != null) {
            if (cur.val <= p.val) {//当前cur节点的值小于等于p节点的值，则说明往当前节点的右边去找
                cur = cur.right;//存在右节点，则一直向下找，因为该节点肯定排在最后
            } else {//当前cur节点的值大于p节点的值，则说明往当前节点的左边去找
                ans = cur;
                cur = cur.left;
            }
        }
        return ans;
    }

    public static void main(String[] args) {
        //二叉搜索树
        TreeNode root = new TreeNode(5);
        root.left = new TreeNode(3);
        root.right = new TreeNode(7);
        root.left.left = new TreeNode(1);
        root.left.right = new TreeNode(4);
        root.left.left.left = new TreeNode(0);
        root.left.left.right = new TreeNode(2);
        root.right.left = new TreeNode(6);
        root.right.right = new TreeNode(8);
        root.right.right.right = new TreeNode(9);

        TreeNode p = new TreeNode(6);
        TreeNode treeNode = inorderSuccessor(root, p);
        System.out.println(treeNode == null ? null : String.valueOf(treeNode.val));
    }
}
